For the purposes of this discussion, programmable logic is defined to be digital circuitry of fixed connectivity that can be configured by a user to emulate other digital systems of arbitrary topologies at high speed. It can be used to create high speed logic simulators as well as configurable compute engines capable of outperforming supercomputers at certain tasks for a fraction of the cost. Programmable logic systems capable of emulating large digital circuits (with hundreds of thousands of gates) are expensive, typically costing on the order of one to two dollars per emulated gate, and require a large number of integrated circuits distributed across multiple, complex printed circuit boards.
One class of programmable logic is based on Field Programmable Gate Array (FPGA) technology. The basic idea behind this approach is to connect a number of FPGAs together in a fixed topology. Each FPGA includes two types of resources: (1) a number of logic cells which can be programmed or configured to perform a specific logic function (such as "AND" or "EXCLUSIVE OR"); and (2) routing resources which can be programmed to interconnect the logic cells with each other and with external input/output pins. The programmed FPGA thus forms a useful logic circuit which is a subset of the entire logic system to be simulated; the entire set of FPGAs taken together then functionally simulates the desired logic system. Since the FPGAs in these architectures have fixed physical connections among them that cannot be altered, simulating a logic system requires a mapping of the circuit for the logic system of interest onto the interconnected FPGAs such that the logic functions and interconnections of the original circuit are precisely represented by the programming of the FPGAs. High speed simulation is possible since the logic cells within the FPGAs perform their computations in parallel, communicating their results with each other through the routing network.
Designing programmable logic capable of high capacity (greater than 1,000,000 gates) and speed (a clock rate greater than 1 MHz) presents several, often conflicting, challenges. First, mapping or "compiling" an arbitrary logic system onto the fixed topology is a difficult and potentially computationally expensive procedure. This problem is substantially reduced if the architecture allows the mapping problem to be broken into a set of simpler, loosely coupled subproblems.
Second, because a generic, programmable structure is being used for emulating a wide variety of possible user designs or algorithms, there is considerably more routing and logic "overhead" than there would be in an optimized layout of the user's design. This overhead must be contained within reasonable bounds while still providing a compilable target.
Third, the design of the architecture and its implementation are necessarily coupled when optimizing data paths for delay.
Finally, the topology and physical organization of the architecture directly affects the difficulty of its implementation. Regular structures with simple interconnections are easier to build.
These problems are best addressed by logic structures that utilize a hierarchical structure for the routing structure network. The routing structure consists of a tree of routing circuits. The root node of the tree provides the input and output lines for the FPGA. The leaf nodes of the tree are connected to the logic cells.
It would be advantageous to provide such a structure on a single wafer to minimize the number of external connections. Prior art architectures of programmable logic systems have been found lacking in their adaptability to wafer scale integration. In prior art systems, the routing function has been implemented in separate router chips. That is, the system was constructed from two classes of basic chips, routers and logic chips. This approach has two main drawbacks when applied to designs requiring wafer-scale implementation. First, if the topology of the system is changed, the wafer must be completely redesigned. For example, if one were to design a system with a different number of levels in the tree routing structure, the size and shape of all of the routing cells would need to be changed. The new cells would then have to be fitted onto the wafer.
Second, this type of design has difficulty accommodating component failures. One important aspect of wafer scale integration is the need to accommodate component fabrication errors. Typically, additional components are provided and some means of substituting the additional components for the failed components is provided. Alternatively, the system should be able to function adequately without one or more of the components, provided the locations of the non-operative components is known.
Broadly, it is the object of the present invention to provide an improved FPGA system.
It is a further object of the present invention to provide an FPGA system that is more easily adapted to wafer scale integration than prior art FPGA systems.
It is a still further object of the present invention to an FPGA that can be constructed from a single sub-unit.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.